查找算法 二分查找
二分查找是什么?
在计算机科学中,二分搜索(binary search),也称折半搜索(half-interval search)、对数搜索(logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分查找的时间复杂度是 (注意,不写底数就是默认以 2 为底),因为二分查找是每次都折半的,所以很明显是 logn 的时间复杂度
非递归方式代码实现
采用非递归方式完成二分查找法。Java 代码如下所示。
public class BinarySearch {
public static void main(String[] args) {
int[] array = new int[]{-7, -4, -2, 5, 8, 10};
System.out.println("原始数据:" + Arrays.toString(array));
int index = binarySearch(array, 8);
System.out.println("【非递归方式二分查找】结果下标位置:" + index);
}
/**
* 二分查找
*/
public static int binarySearch(int[] array, int value) {
int mid;
int start = 0;
int end = array.length - 1;
while (start <= end) {
mid = (end - start) / 2 + start;
// 说明在左边
if (value < array[mid]) {
end = mid - 1;
}
// 说明在右边
else if (value > array[mid]){
start = mid + 1;
} else {
return mid;
}
}
return -1;
}
}
递归方式代码实现
采用递归方式完成二分查找算法。代码如下所示。
/**
* @author alsritter
* @version 1.0
**/
public class BinarySearch {
public static void main(String[] args) {
int[] array = new int[]{-7, -4, -2, 5, 8, 10};
System.out.println("原始数据:" + Arrays.toString(array));
int index = binarySearch(array, 8, 0, array.length - 1);
System.out.println("【递归方式二分查找】结果下标位置:" + index);
}
/**
* 递归的二分查找
*/
public static int binarySearch(int[] array, int value, int start, int end) {
int mid = (end - start) / 2 + start;
if (array[mid] == value) return mid;
if (start >= end) {
return -1;
}
// 说明在左边
else if (value < array[mid]) {
return binarySearch(array, value, start, mid - 1);
}
// 说明在右边
else if (value > array[mid]) {
return binarySearch(array, value, mid + 1, end);
}
return -1;
}
}
有序数组查找多个结果
当一个有序数组中,有多个相同的数值时,如何将所有的数值都查找到
{1, 8, 10, 89, 1000, 1000, 1234} 如这里的 1000
思路分析:
- 在找到 mid 索引值,不要马上返回
- 向 mid 索引值的左边扫描,将所有满足 1000 的元素下标,加入到集合中(ArrayList)
- 向 mid 索引值的右边扫描,将所有满足 1000 的元素下标,加入到集合中(ArrayList)
- 将 ArrayList 返回
/**
* 二分查找顺序数组的多个结果
*/
public static List<Integer> binarySearch2(int[] array, int value) {
int mid;
int start = 0;
int end = array.length - 1;
ArrayList<Integer> result = new ArrayList<>();
while (start <= end) {
mid = (end - start) / 2 + start;
// 说明在左边
if (value < array[mid]) {
end = mid - 1;
}
// 说明在右边
else if (value > array[mid]) {
start = mid + 1;
} else {
// 到了这里表示已经找到目标值了
int temp = mid - 1;
// 先检查左边的
while (temp >= 0 && array[temp] == value) {
// 否则就 temp 放入到 result 里面
result.add(temp);
temp--; // 左移
}
// 再检查右边的
while (temp <= array.length - 1 && array[temp] == value) {
// 否则就 temp 放入到 result 里面
result.add(temp);
temp++; // 右移
}
}
}
return result;
}
链表的二分查找:跳跃表
补充一个链表的二分查找:跳跃表
局部最小问题
题目:给定一个无序数组,并且相邻两个元素不相等,返回任意一个局部最小值
局部最小值的定义为:
- 对于第一个元素而言,只要它比第二个元素要小,则就是局部最小值。
- 同理,对于最后一个元素而言,只要它比倒数第二个元素要小,则就是局部最小值。
- 对于数据中间的元素,如果一个数相邻的两个数都比他大,那么他就是局部最小值。
这里解释一下第三种情况,如果上面两种情况都不满足就是如下图这样
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] A = {19, 11, 3, 8, 10};
System.out.println(BinarySearch(A));
}
private static int BinarySearch(int[] nums) {
// 规定当数组中只有一个数时,不存在局部最小值
if (nums == null || nums.length <= 1) {
return 0;
}
int len = nums.length;
if (nums[0] < nums[1]) {
return nums[0];
}
if (nums[len - 1] < nums[len - 2]) {
return nums[len - 1];
}
int start = 0;
int end = len - 1;
// 还是可以使用二分法
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] > nums[mid + 1]) {
start = mid + 1;
} else {
end = mid;
}
}
return (nums[start] < nums[start + 1]) ? nums[start] : nums[end];
}
}